package leetcode.Hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
 * <p>
 * 说明：拆分时可以重复使用字典中的单词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/18 10:52
 * @see coinChange1
 * 面试题
 * 还有其它解法 DFS或 BFS
 */
public class wordBreak1 {

    public static void main(String[] args) {

        List<String> wordDict = new ArrayList<>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("aaa");
        wordDict.add("aaaa");
        wordDict.add("aaaaa");
        wordDict.add("aaaaaa");
        wordDict.add("aaaaaaa");
        wordDict.add("aaaaaaaa");
        wordDict.add("aaaaaaaaa");
        wordDict.add("aaaaaaaaaa");

        System.out.println(wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", wordDict));
    }

    // 完全背包问题
    // 动态规划状态定义：boolean[] dp，dp[i] 表示s 的前i个元素 能否拆解成 字典中的单词，所以 d[s.length] 表示 s 能否拆解成字典中的单词。那么数组dp的大小为 length + 1
    // 动态规划初始值 ： dp[0] 表示s 的前0个元素能否拆解成 字典中的单词，对于边界条件，我们定义 dp[0] =true  表示空串且合法。
    // 动态规划转移方程：dp[i] = dp[j](true) +  wordDictSet.contains(substring(j, i))
    // 时间复杂度：O(n^2)
    // 空间复杂度：O(n)
    static boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = dp[j] && wordDictSet.contains(s.substring(j, i));
                if (dp[i]) break;
            }
        }
        return dp[s.length()];
    }

    // 思考 内层循环是否可以换成 循环wordDictSet，判断s.endWith(word), 然后再找 dp[i- word.length] 是否为true，由此判断dp[i]的真假
    // 因为 coinChange 的内层循环就是 以 coins为内层循环进行的，将 时间复杂度 O(amount^2)降为 O(amount * coins.length)
    // 这里内层循环是否使用 物品种类（wordDict中的word，coins中的coin 都对应完全背包问题的物品），取决于 物品种类数目 和 背包容量 的大小比较
    // 结合实际场景来看，硬币的种类一般是有限的，并且通常比amount小，所以内存循环使用 coins 更优；
    // 字典的单词数一般是有限的，并且通常比s.length 更大，所以内存循环使用 s.length 更优

}
